//
// Created by yangchao on 2022/7/10.
// 215. 数组中的第K个最大元素 https://leetcode.cn/problems/kth-largest-element-in-an-array/
//
#include <vector>
using namespace std;

class FindKthLargest {
public:
    int findKthLargest(vector<int>& nums, int k) {
        heapSort(nums);
        return nums[nums.size()-k];
    }

    //堆排序
private:
    void heapSort(vector<int>& array) {
        int temp = 0;
        //将无序序列构建成一个大顶堆: 从最后一个非叶子节点开始
        int len = array.size();
        for (int i = len/ 2 - 1; i >= 0 ; i--) {
            adjustHeap(array,i,len);
        }
        //将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
        //重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
        for (int i = len-1; i > 0; i--) {
            temp = array[i];
            array[i] = array[0];
            array[0] = temp;
            adjustHeap(array,0,i);
        }
    }
    void adjustHeap(vector<int>& array, int i, int length) {
        //先把当前元素取出来，因为当前元素可能要一直移动
        int temp = array[i];
        for (int k = i*2+1; k < length; k = 2*k+1) {
            if (k+1 < length && array[k] < array[k+1]) {
                k++;         //取出左右子节点中的最大值
            }
            if (array[k] > temp) {
                array[i] = array[k];
                i = k;    //确定tmp值要存放的位置
            } else {
                break;
            }
        }
        array[i] = temp;
    }
};
